import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NQueens {
    /*
    * 51. N 皇后
    * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
    * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
    * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
    * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
    *
    * 1 <= n <= 9
    * */
    public static void main(String[] args){
        NQueens o = new NQueens();
        o.mySolution(4);
        System.out.println(o.res);
    }

    // 我的想法：
    public List<List<String>> mySolution(int n){
        res = new ArrayList<>(n);
        board = new char[n][n];
        for (int i = 0; i < board.length; i++) {
            Arrays.fill(board[i], '.');
        }
        backTracing(0);
        return res;
    }

    List<List<String>> res;
    char[][] board;

    // 每次尝试在本行放置一个皇后，若可以放置，然后再向下一行放
    private void backTracing(int start){
        // 这里处理结果写法可以优化
        if(start >= board.length){
            ArrayList<String> r = new ArrayList<>(board.length);
            for (int i = 0; i < board.length; i++) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < board.length; j++) {
                    builder.append(board[i][j]);
                }
                r.add(builder.toString());
            }
            res.add(r);
//            ArrayList<String> r = new ArrayList<>(board.length);
//            for (char[] c : board){
//                r.add(String.copyValueOf(c));
//            }
//            res.add(r);
            return;
        }

        for (int i = 0; i < board.length; i++) {
            if(isValid(start, i)){
                board[start][i] = 'Q';
                backTracing(start+1);
                board[start][i] = '.';
            }
        }
    }

    // 判断当前位置能否放置皇后，因为当前行一定是最新的行，且只有一个皇后，
    // 不必判断该行，只需判断列、45°向上，135°向上即可
    private boolean isValid(int row, int col){
        // 判断列
        for (int i = 0; i < row; i++) {
            if(board[i][col] == 'Q')
                return false;
        }
        // 判断45°向上
        int i = row - 1;
        int j = col + 1;
        while (i >= 0 && j < board.length){
            if(board[i][j] == 'Q')
                return false;
            i--;
            j++;
        }
        // 判断135°向上
        i = row - 1;
        j = col - 1;
        while (i >= 0 && j >= 0){
            if(board[i][j] == 'Q')
                return false;
            i--;
            j--;
        }
        return true;
    }

}
